package com.yang.Offer;

import java.util.HashSet;
import java.util.Set;

/**
 * @Author: yang
 * @Description: 输入一个字符串，打印出该字符串中字符的所有排列。
 * 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素
 *
 * 全排列，不能重复所以使用HashSet  然后通过递归回溯遍历所有排列 再进行剪枝操作
 *
 * @Date: Created in 17:31 2022/8/3
 * @Modified By:
 */
public class Offer38 {
}

class Offer38Solution {
    boolean[] visited;
    Set<String> list;
    public String[] permutation(String s) {
        visited = new boolean[s.length()];
        list = new HashSet<>();
        char[] ch = s.toCharArray();
        dfs(ch, "");
        return list.toArray(new String[0]);
    }
    public void dfs(char[] arr, String s){
        if(s.length() == arr.length){
            list.add(s);
            return;
        }
        for(int i = 0; i <arr.length; i++){
            // 去重(防止多循环会导致同一个位置的字符一直添加length次)
            if(visited[i]) continue;
            if (i > 0 && arr[i] == arr[i - 1] && visited[i - 1] == false) {
                continue;
            }
            visited[i] = true;
            dfs(arr, s+String.valueOf(arr[i]));
            visited[i] = false;
        }
    }
}
